package com.learn.algorithm.sort;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

/**
 * @author wangxing
 * @version 2020/7/11 12:58 Administrator
 */
public class Sort {
    /**
     * 获得乱序数组
     *
     * @param size 数组长度
     * @param max  数组内容范围 1到 max
     * @return 指定范围乱序数组
     */
    public static int[] getOutOfOrderArr(int size, int max) {
        int[] arr = new int[size];
        Random r = new Random();
        int temp;
        for (int i = 0; i < size; i++) {
            temp = r.nextInt(max);
            if (temp == 0) {
                temp = r.nextInt(max);
            }
            arr[i] = temp;
        }
        return arr;
    }

    /**
     * 33选7,16选1
     *
     * @return 33选7, 16选1
     */
    public static int[] getLotteryRed33Blue16() {
        int[] arr = new int[7];
        HashSet<Integer> redNum = new HashSet<>(10);
        arr[6] = 100;
        redNum.add(0);
        int redTemp;
        Random r = new Random();
        for (int i = 0; i < 6; i++) {
            redTemp = r.nextInt(33);
            while (redNum.contains(redTemp)) {
                redTemp = r.nextInt(33);
            }
            arr[i] = redTemp;
        }
        Arrays.sort(arr);
        arr[6] = r.nextInt(16);
        while (arr[6] == 0) {
            arr[6] = r.nextInt(16);
        }
        return arr;
    }

    /**
     * 冒泡排序
     * 两两比较待排序的数字,并交换不满足次序要求的数字,直到整个数组都满足要求为止
     * 交换类型排序
     * 平均时间复杂度O(N^2)
     * 最坏时间复杂度O(N^2)
     * 空间复杂度O(1)
     * 稳定算法
     * 复杂性简单
     *
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        int temp;
        int l = arr.length;
        for (int i = 0; i < l; i++) {
            for (int j = l - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
//            System.out.format("第%d趟:\t", i);
//            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 冒泡排序优化版本,在确认没有进行顺序调整后,将不在进行之后的排序
     * 交换类型排序
     * 平均时间复杂度O(N^2)
     * 最坏时间复杂度O(N^2)
     * 时间复杂度最好情况O(N) (数组有序的情况下)
     * 空间复杂度O(1)
     * 稳定算法
     * 复杂性简单
     *
     * @param arr 待排序数组
     */
    public static void bubbleOptimizeSort(int[] arr) {
        int temp;
        int l = arr.length;
        for (int i = 0; i < l; i++) {
            boolean f = false;
            for (int j = l - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    f = true;
                }
            }
            if (!f) {
                break;
            }
//            System.out.format("第%d趟:\t", i);
//            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 快速排序
     * 交换类型排序
     * 平均时间复杂度O(NLog2N)
     * 最坏时间复杂度O(N^2)
     * 最好时间复杂度O(NLog2N)
     * 空间复杂度O(NLog2N)
     * 非稳定排序
     * 复杂度较复杂
     *
     * @param arr 待排序数组
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int t = quickSortMain(arr, left, right);
//            System.out.println(Arrays.toString(arr));
//            System.out.println("base = " + t);
            quickSort(arr, left, t - 1);
            quickSort(arr, t + 1, right);
        }
    }

    /**
     * 通过一次排序将要排序的数组分成左右两部分,分割点左侧的数字都要小于分割点,分割点右侧的数字都要小于分割点,而后在分别对分割点两侧的新数列进行相同的操作
     * 结束的条件是遍历后左侧index不再小于右侧index
     *
     * @param arr   待排序数组
     * @param left  左端索引
     * @param right 右端索引
     * @return 返回更新完位置后, 左端是索引位置
     */
    private static int quickSortMain(int[] arr, int left, int right) {
        int temp = arr[left];
        while (left < right) {
            //比较当前值和右边界的数字,如果当前值小于右边界值则右边界值向左移动,直到出现当前值大于右边界值
            while (left < right && arr[right] >= temp) {
                right--;
            }
            //进行交换,将右边界内找到的第一个比左侧值小的数字和左侧数字交换
            arr[left] = arr[right];
            //比较当前数字和左边界的数字,如果当前数字大于等于左边界,则左边界向右移动,直到出现当前值小于左边界值
            while (left < right && arr[left] <= temp) {
                left++;
            }
            //进行交换,将左边界内找到的第一个比当前数字大的数字移动到右边界内
            arr[right] = arr[left];
        }
        arr[left] = temp;
        return left;
    }

    /**
     * 插入排序
     * 每次比较当前数组中当前要比较数字与之前已经确认过顺序数字的的大小,如果比前一个大就交换位,直到出现一个比当前数字小的数字停止当前交换
     * 原理,是当前数字之前的数字都是已经有序的,所以出现一个比当前数字小的数,那么前面的都会比这个数字小,也就不需要再做判定了
     * <p>
     * 插入类型排序
     * 平均时间复杂度O(N^2)
     * 最坏时间复杂度O(N^2)
     * 最好时间复杂度O(N)
     * 空间复杂度O(1)
     * 稳定排序
     * 复杂性简单
     *
     * @param arr 待排序数组
     */
    public static void insertSort(int[] arr) {
        for (int i = 1, l = arr.length; i < l; i++) {
            int j;
            int temp = arr[i];
            for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                arr[j + 1] = arr[j];
            }
            arr[j + 1] = temp;
        }
    }

    /**
     * 希尔排序
     * 把记录按照步长gap分组,对每组数据进行直接插入排序,整个数组在步长减小的过程中逐步趋近于有序,
     * 当最后步长为1时整个数组基本已经趋近有序,做直接插入排序效率最高
     * 插入型排序
     * 平均时间复杂度O(NLog2N)
     * 最坏时间复杂度O(N^1.5)
     * 最好时间复杂度O(N)
     * 空间复杂度(1)
     * 非稳定排序
     * 较复杂
     *
     * @param arr 待排序数组
     */
    public static void shellSort(int[] arr) {
        int l = arr.length;
        //定义步长为当前数组的一半
        int gap = l / 2;
        //当步长小于1后的时候终止循环
        while (gap >= 1) {
            //从步长开始向下依次循环
            for (int i = gap; i < l; i++) {
                int j;
                int temp = arr[i];
                //每次进行步长中数据的比较
                for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
            gap /= 2;
        }
    }

    /**
     * 选择排序
     * 每次从待排序的数据中选择一个最小的值放到数组待排序数据最左端,然后依次执行,到数组最右端,数组变为有序
     * <p>
     * 选择型排序
     * 平均时间复杂度O(N^2)
     * 最坏时间复杂度O(N^2)
     * 最好时间复杂度O(N^2)
     * 空间复杂度O(*1)
     * 非稳定排序
     * 简单
     *
     * @param arr 待排序数组
     */
    public static void selectSort(int[] arr) {

        for (int i = 0, l = arr.length; i < l; i++) {
            int min = arr[i];
            int index = i;
            for (int j = i + 1; j < l; j++) {
                if (min > arr[j]) {
                    index = j;
                    min = arr[j];
                }
            }
            arr[index] = arr[i];
            arr[i] = min;
        }
    }

    /**
     * 堆排序
     *
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr) {
        int length = arr.length;
        for (int i = length / 2; i >= 0; i--) {
            createHeap(arr, i, length);
        }
        for (int i = length - 1; i > 0; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            createHeap(arr, 0, i);
        }

    }

    /**
     * 建立小根堆
     *
     * @param arr    待排序数组
     * @param parent 父节点
     * @param length 长度
     */
    private static void createHeap(int[] arr, int parent, int length) {
        int temp = arr[parent];
        int child = 2 * parent + 1;
        while (child < length) {
//            如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (child + 1 < length && arr[child] < arr[child + 1]) {
                child++;
            }
//            如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arr[child]) {
                break;
            }
//            把孩子结点的值赋给父结点
            arr[parent] = arr[child];
            parent = child;
//            选取孩子结点的左孩子结点,继续向下筛选
            child = 2 * child + 1;
        }
        arr[parent] = temp;
    }

    static int[] arr2;

    /**
     * 归并排序
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        arr2 = new int[arr.length];
        for (int gap = 1; gap < arr.length; gap = 2 * gap) {
            MergePass(arr, gap, arr.length);
        }
    }

    public static void Merge(int[] array, int low, int mid, int high) {
        int i = low; // i是第一段序列的下标
        int j = mid + 1; // j是第二段序列的下标
        int k = 0; // k是临时存放合并序列的下标
        int[] array2 = new int[high - low + 1]; // array2是临时合并序列

        // 扫描第一段和第二段序列，直到有一个扫描结束
        while (i <= mid && j <= high) {
            // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
            if (array[i] <= array[j]) {
                array2[k] = array[i];
                i++;
            } else {
                array2[k] = array[j];
                j++;
            }
            k++;
        }

        // 若第一段序列还没扫描完，将其全部复制到合并序列
        while (i <= mid) {
            array2[k] = array[i];
            i++;
            k++;
        }

        // 若第二段序列还没扫描完，将其全部复制到合并序列
        while (j <= high) {
            array2[k] = array[j];
            j++;
            k++;
        }

        // 将合并序列复制到原始序列中
        for (k = 0, i = low; i <= high; i++, k++) {
            array[i] = array2[k];
        }
    }

    public static void merge(int[] arr, int low, int mid, int high) {
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                arr2[k] = arr[i];
                i++;
            } else {
                arr2[k] = arr[j];
                j++;
            }
            k++;
        }
        while (j <= mid) {
            arr2[k] = arr[i];
            i++;
            k++;
        }
        while (j <= high) {
            arr2[k] = arr[j];
            j++;
            k++;
        }
        // 将合并序列复制到原始序列中
        for (k = 0, i = low; i <= high; i++, k++) {
            arr[i] = arr2[k];
        }
    }

    public static void MergePass(int[] array, int gap, int length) {
        int i = 0;

        // 归并gap长度的两个相邻子表
        for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
            Merge(array, i, i + gap - 1, i + 2 * gap - 1);
        }

        // 余下两个子表，后者长度小于gap
        if (i + gap - 1 < length) {
            Merge(array, i, i + gap - 1, length - 1);
        }
    }
}
